public class Main {
    /**
     * 判断一颗树是否是平衡二叉树
     */
//    public class Solution {
//        public boolean IsBalanced_Solution (TreeNode pRoot) {
//            if(pRoot == null) return true;
//            return dfs(pRoot) == -1 ? false : true;
//        }
//        int dfs(TreeNode root) {
//            if(root == null) return 0;
//            int x = dfs(root.left);
//            if(x == -1) return -1;//剪枝
//            int y = dfs(root.right);
//            if(y == -1) return -1;
//            return Math.abs(x - y) > 1 ? -1 : Math.max(x, y) + 1;
//
//        }
//    }


/**
 * 小葱的01串
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            char[] s = in.next().toCharArray();
//            //先统计一下总的0的个数
//            int a = 0;
//            for (char ch : s) {
//                if (ch == '0') a++;
//            }
//            //滑动窗口
//            int left = 0;
//            int right = 0;
//            int half = n / 2;
//            int ret = 0;
//            int b = 0;//统计一下窗口内0个个数
//            //细节: right 不能移到n - 1 因为前面已经算过一次了
//            while (right < n - 1) {
//                //入窗口
//                if(s[right] == '0') b++;
//                //出窗口
//                while(right - left + 1 > half) {
//                    if(s[left++] == '0') b--;
//                }
//                //更新结果
//                if(right - left + 1 == half) {
//                    if(b * 2 == a) {
//                        ret += 2;
//                    }
//                }
//                right++;
//            }
//            System.out.println(ret);
//        }
//    }


    /**
     * 最大子矩阵
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int[][] arr = new int[n + 1][n + 1];
//            int[][] dp = new int[n + 1][n + 1];
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <=n; j++) {
//                    arr[i][j] = in.nextInt();
//                }
//            }
//            //初始化DP
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= n; j++) {
//                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
//                }
//            }
//            int ret = -127;
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= n; j++) {
//                    for (int k = i; k <= n; k++) {
//                        for (int l = j; l <= n; l++) {
//                            int x1 =  i;
//                            int y1 = j;
//                            int x2 = k;
//                            int y2 = l;
//                            //计算面积
//                            int area = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
//                            ret = Math.max(ret, area);
//                        }
//                    }
//                }
//            }
//            System.out.println(ret);
//        }
//    }


/**
 * 链表相加
 */
//    public class Solution {
//        //翻转链表
//        public ListNode reverse(ListNode head) {
//            //头插法
//            ListNode newHead = new ListNode(0);//虚拟头结点
//            ListNode cur = head;
//            while (cur != null) {
//                ListNode curNext = cur.next;
//                cur.next = newHead.next;
//                newHead.next = cur;
//                cur = curNext;
//            }
//            return newHead.next;
//        }
//
//        public ListNode addInList (ListNode head1, ListNode head2) {
//            ListNode cur1 = reverse(head1);
//            ListNode cur2 = reverse(head2);
//            int t = 0;
//            ListNode ret = new ListNode(0);
//            ListNode tail = ret;//用来指向每次插入的尾部
//            while (cur1 != null || cur2 != null || t != 0) {
//                if (cur1 != null) {
//                    t += cur1.val;
//                    cur1 = cur1.next;
//                }
//                if (cur2 != null) {
//                    t += cur2.val;
//                    cur2 = cur2.next;
//                }
//                tail.next = new ListNode(t % 10);
//                t /= 10;
//                tail = tail.next;
//            }
//            return reverse(ret.next);
//        }
//    }

/**
 * 球最小公倍数
 */
//public class Main {
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int a = in.nextInt();
//        int b =  in.nextInt();
//        System.out.println(a * b / gcd(a, b));
//    }
//    //先求两数的最大公约数
//    public static int gcd(int a, int b) {
//        if (b == 0) return a;
//        return gcd(b, a % b);
//    }
//}

    /**
     * 拼三角
      */
//    public class Main{
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int t = in.nextInt();
//            while(t-- > 0) {
//                int[] arr = new int[6];
//                for(int i = 0;i < 6;i++) {
//                    arr[i] = in.nextInt();
//                }
//                Arrays.sort(arr);
//                if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5]) {
//                    System.out.println("Yes");
//                    continue;
//                }
//                if(arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5]) {
//                    System.out.println("Yes");
//                    continue;
//                }
//                if(arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5]) {
//                    System.out.println("Yes");
//                    continue;
//                }
//                if(arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3]) {
//                    System.out.println("Yes");
//                    continue;
//                }
//                System.out.println("No");
//            }
//        }
//
//    }


/**
 * 字母收集
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int m = in.nextInt();
//            char[][] grid = new char[n + 1][m + 1];
//            for (int i = 1; i <= n; i++) {
//                String s = in.next();
//                for (int j = 1; j <= m; j++) {
//                    grid[i][j] = s.charAt(j - 1);
//                }
//            }
//            int[][] dp = new int[n + 1][m + 1];
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= m; j++) {
//                    int t = 0;
//                    if (grid[i][j] == 'l') t = 4;
//                    else if (grid[i][j] == 'o') t = 3;
//                    else if (grid[i][j] == 'v') t = 2;
//                    else if (grid[i][j] == 'e') t = 1;
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + t;
//                }
//            }
//            System.out.println(dp[n][m]);
//        }
//    }


/**
 * 数组中的最长连续子序列
 */
//    public class Solution {
//        public int MLS (int[] arr) {
//            Arrays.sort(arr);
//            int n = arr.length;
//            int ret = 0;
//            for (int i = 0; i < n;) {
//                int count = 1;
//                int j = i + 1;
//                while (j < n) {
//                    int tmp = arr[j] - arr[j - 1];
//                    if (tmp == 1) {
//                        count++;
//                        j++;
//                    } else if (tmp == 0) {
//                        //跳过重复的数
//                        j++;
//                    } else {
//                        //连续的数间断
//                        break;
//                    }
//                }
//                ret = Math.max(ret, count);
//                i = j;
//            }
//            return ret;
//        }
//    }

/**
 * 字母收集
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int m = in.nextInt();
//            char[][] grid = new char[n + 1][m + 1];
//            for (int i = 1; i <= n; i++) {
//                String s = in.next();
//                for (int j = 1; j <= m; j++) {
//                    grid[i][j] = s.charAt(j - 1);
//                }
//            }
//            int[][] dp = new int[n + 1][m + 1];
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= m; j++) {
//                    int t = 0;
//                    if (grid[i][j] == 'l') t = 4;
//                    else if (grid[i][j] == 'o') t = 3;
//                    else if (grid[i][j] == 'v') t = 2;
//                    else if (grid[i][j] == 'e') t = 1;
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + t;
//                }
//            }
//            System.out.println(dp[n][m]);
//        }
//    }




}


